class Solution:
	# @param dungeon, a list of lists of integers
	# @return a integer
	def calculateMinimumHP(self, dungeon):
		n = len(dungeon)
		m = len(dungeon[0])
		if n == 1 and m == 1:
			return max(1-dungeon[0][0], 1)
		path_list = self.generate(n, m)
		maxi = None
		for path in path_list:
			cur = self.calculate(path, dungeon)
			if maxi is None:
				maxi = cur
			else:
				maxi = max(maxi, cur)
		return max(1 - maxi, 1)

		
	def generate(self, n, m):
		cur = "0"*(m-1) + "1"*(n-1)
		ans = [cur]
		if m == 1 or n == 1:
			return ans
		while True:
			cl = list(cur)
			first = None
			for i in xrange(len(cl)-2, -1, -1):
				if cl[i+1] == "1" and first is None:
					first = i+1
				if cl[i] == '0' and cl[i+1] == "1":
					cl[i] = '1'
					cl[first] = '0'
					cl[i+1:] = cl[-1:i:-1]
					cur = "".join(cl)
					ans.append(cur)
					break
				if i == 0:
					return ans

	def calculate(self, path, dungeon):
		blood = dungeon[0][0]
		mini = min(dungeon, 1)
		r, c = 0, 0
		for ch in path:
			if ch == '1':
				r += 1
			else:
				c += 1
			blood += dungeon[r][c]
			mini = min(mini, blood)
		return mini




if __name__ == '__main__':
	so = Solution()
	dun = [
		[1,-3,3],[0,-2,0],[-3,-3,-3]
	]
	print so.calculateMinimumHP(dun)
